package com.cn.algorithm02.class21;

/***
 * @author: hels
 * @description: 象棋盘 横9*竖10，马走日从(0,0)经过k步刚好跳到(7,7)有多少种方法
 **/
public class C02_HorseJump {
    public static void main(String[] args) {
        System.out.println(jump(7, 7, 10));
        System.out.println(jump2(7, 7, 10));

    }


    // 递归方法
    public static int jump(int a, int b, int k) {
        return process(0, 0, k, a, b);
    }

    public static int process(int x, int y, int rest, int a, int b) {
        // basic case
        if (x < 0 || x > 8 || y < 0 || y > 9) {
            return 0;
        }
        if (rest == 0) {
            return (x == a && y == b) ? 1 : 0;
        }

        int ways = process(x + 1, y + 2, rest - 1, a, b);
        ways += process(x + 2, y + 1, rest - 1, a, b);
        ways += process(x + 2, y - 1, rest - 1, a, b);
        ways += process(x + 1, y - 2, rest - 1, a, b);
        ways += process(x - 1, y - 2, rest - 1, a, b);
        ways += process(x - 2, y - 1, rest - 1, a, b);
        ways += process(x - 2, y + 1, rest - 1, a, b);
        ways += process(x - 1, y + 2, rest - 1, a, b);
        return ways;
    }

    // 动态规划
    public static int jump2(int a, int b, int k) {
        int[][][] dp = new int[9][10][k + 1];
        dp[a][b][0] = 1;
        for (int rest = 1; rest <= k; rest++) {
            for (int x = 0; x < 9; x++) {
                for (int y = 0; y < 10; y++) {
                    dp[x][y][rest] = pickNum(dp, x + 1, y + 2, rest - 1);
                    dp[x][y][rest] += pickNum(dp, x + 2, y + 1, rest - 1);
                    dp[x][y][rest] += pickNum(dp, x + 2, y - 1, rest - 1);
                    dp[x][y][rest] += pickNum(dp, x + 1, y - 2, rest - 1);
                    dp[x][y][rest] += pickNum(dp, x - 1, y - 2, rest - 1);
                    dp[x][y][rest] += pickNum(dp, x - 2, y - 1, rest - 1);
                    dp[x][y][rest] += pickNum(dp, x - 2, y + 1, rest - 1);
                    dp[x][y][rest] += pickNum(dp, x - 1, y + 2, rest - 1);
                }
            }

        }
        // dp返回结果要参考递归的额开始参数
        return dp[0][0][k];
    }

    public static int pickNum(int[][][] dp, int x, int y, int rest) {
        // basic case
        if (x < 0 || x > 8 || y < 0 || y > 9) {
            return 0;
        }
        return dp[x][y][rest];
    }

}
